Task Scheduling (due November 5^th)

You are given N types of tasks with (possibly) different completion times t_i, initial costs c_i, and initial values v_i (i = 0, 1, ..., N-1). Your aim is to determine a set of tasks and the optimum order of doing these tasks so that total value of the chosen tasks is maximized, total running time is not more than a given integer T and total cost is not more than a given integer C. There are infinitely many tasks of each type, i.e., you can use any number of tasks of each type.

Total time T is divided into intervals of length T_interval, i.e., T = kT_interval for some integer k. During the first time interval, interval₀, each task i has value v_i and cost c_i but these numbers change over time such that at each interval change, and for each i = 0, 1, ..., N-1,  v_i is decrement by 1 (until they reach zero) and cost c_i is incremented by 1, i.e., during interval_j, value of task i is (v_i-j) if v_i > j and 0 if v_i £ j (for all j = 0, 1, 2, ..., k-1). Values and costs change only at the time moments between intervals (at time moments T_interval, 2T_interval , 3T_interval, ..., (k-1)T_interval) but not during intervals, where the task execution starts at moment 0. Tasks of the same type can be used in different time intervals and their values and costs will not be same in this case. 

There can be time periods when no task is being executed. Also, tasks should end in the interval that they are started in, i.e., no task should be continuing execution at time moments between intervals but they can be started or ended at these time moments.

In part one, you need to give only the maximal value of the chosen tasks in your optimal solution. Part one is 65% of the homework.

In part two, the order of the chosen tasks should also be given in the output. Part two is 35%.

Assumptions

1 £ N £ 100

1 £ C £ 1000

1 £ T £ 1000

(T / 10) £ T_interval £ 100

1 £ v_i £ 100

1 £ t_i £ T_interval

1 £ c_i £ C

These given numbers are all integers.

Input data is error-free, no need to check for correctness.

Input

The input file is named task.inp. The first line of this file contains four integers, corresponding to N, T, C, and T_interval, respectively. In each the following N lines (ordered by task type number i = 0, 1, ..., N-1), there are three integers representing completion time t_i, initial cost c_i, and initial value v_i, respectively. So, the 2nd line of the file corresponds to task type 0, the 3rd line corresponds to task type 1, and so on. The integers in the same line are separated by a single space.

Output

The output file is named task.out. There should be only integers in the output file. The first line of this file should contain a single integer representing the total value of tasks in the optimal solution found (for part one). If you also solve part two, then there should be M+1 more lines in the same output file, where M is the total number of tasks executed. M should be given in the second line of the output file. Each of the lines 3, 4, ..., M+2 correspond to a task and should contain two integers representing the type and the starting time moment of the task, respectively, separated by a space character. These M lines should be ordered by their starting moments. There may be more than one optimal solutions giving the same total value. You only need to give one of these solutions.

Example

(Hint: This homework is a more complex version of the Knapsack Problem, which can be solved using Dynamic Programming.)